package com.sjc.algorithm.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author by SangJiacun
 * @Date 2020/5/11 15:01
 */
public class MyBinaryTree {

    public static void main(String[] args){
        //                  3
        //           2             8
        //     9        10    null   4
        //null null null null
        Integer[] arr = new Integer[]{3,2,9,null,null,10,null,null,8,null,4};
        LinkedList<Integer> list = new LinkedList<>(Arrays.asList(arr));

        TreeNode binaryTree = createBinaryTree(list);
        preOrderPrint(binaryTree);  // 3,2,9,10,8,4
        middleOrderPrint(binaryTree); // 9,2,10,3,8,4
        postOrderPrint(binaryTree); // 9,10,2,4,8,3

    }

    public static TreeNode createBinaryTree(LinkedList<Integer> arrayList){
        if(null == arrayList || arrayList.size()==0){
            return null;
        }
        TreeNode node = null;
        Integer data = arrayList.removeFirst();
        if(null != data){
            node = new TreeNode(data);
            node.left = createBinaryTree(arrayList);
            node.right = createBinaryTree(arrayList);
        }
        return node;
    }

    public static void preOrderPrint(TreeNode node){
        if(null == node){
            return;
        }
        System.out.println(node.data);
        preOrderPrint(node.left);
        preOrderPrint(node.right);
    }

    public static void middleOrderPrint(TreeNode node){
        if(null == node){
            return;
        }

        middleOrderPrint(node.left);
        System.out.println(node.data);
        middleOrderPrint(node.right);
    }

    public static void postOrderPrint(TreeNode node){
        if(null == node){
            return;
        }
        postOrderPrint(node.left);
        postOrderPrint(node.right);
        System.out.println(node.data);
    }

    public static void levelOrderPrint(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.println(node.data);
            if(null != node.left){
                queue.offer(node.left);
            }
            if(null != node.right){
                queue.offer(node.right);
            }
        }
    }

    private static class TreeNode{
        private int data;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int data){
            this.data = data;
        }
    }
}
